package cn.fansunion.leecode.recursion;

/**
 * 441. 排列硬币 <br/>
 * 你总共有 n 枚硬币，并计划将它们按阶梯状排列。<br/>
 * 对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。<br/>
 * 给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。<br/>
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/arranging-coins 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 * @author wen.lei@brgroup.com
 *
 *         2022-3-9
 */
public class ArrangingCoins {
    /*示例 1：
    
    
    输入：n = 5
    输出：2
    解释：因为第三行不完整，所以返回 2 。
    示例 2：
    
    
    输入：n = 8
    输出：3
    解释：因为第四行不完整，所以返回 3 。
     
    
    提示：
    
    1 <= n <= 231 - 1*/

    /**
     * 解题思路：n个数，落在第k行：>=第k行的最大值， <第k+1行的最大值 <br/>
     * 第k行的范围：第k行的最小值，(1+2+3...+k)-(k-1); <br/>
     * 第k行的最大值(1+2+3...+k); <br/>
     */
    public int arrangeCoins(int n) {
        for (int k = 1; k < n; k++) {
            long maxK = fullK(k);
            long maxK1 = maxK + (k + 1);
            // 变种的二分查找，暂不考虑了，代码不好理解，可读性太差
            if (n >= maxK && n < maxK1) {
                return k;
            }
        }
        return 1;
    }

    /**
     * 第k行铺满，i枚硬币 (等差数列，高斯求和)；乘法，应该比for循环的加法快很多
     * 
     * @param k
     * @return
     */
    private long fullK(long k) {
        // 2个数必有一个偶数，肯定能“除尽”
        // int的最大值也太小了，2147483647，2个万相乘就是亿了
        // 输入类型为long，可以支持更大的k；但是如果k太大，也会溢出
        return (1 + k) * k / 2;
    }

    // 返回值用long，也会越界
    private long fullKOverflow2(int k) {
        return (1 + k) * k / 2;
    }

    // 越界了
    private int fullKOverflow(int k) {
        // int的最大值也太小了，2147483647，2个万相乘就是亿了
        return (1 + k) * k / 2;
    }

}
